\documentclass[draft,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage[in]{fullpage}
\usepackage{booktabs}
\usepackage{amsmath}

% DEFINED COMMANDS:
	% a program variable
\providecommand{\var}[1]{\texttt{#1}}
	% the NULL value
\providecommand{\NULL}{NULL}
	% terminator of a string (L'\0')
\providecommand{\strterm}{\texttt{L'\symbol{92}0'}}
	% table head
\providecommand{\thead}[1]{\textbf{{#1}}}
	% a term
\providecommand{\term}[1]{\textit{{#1}}}
	% big O in big-O notation
\providecommand{\bigO}{\ensuremath{\mathcal{O} }}

% \newcommand{\movedown}[2]{%
% 	\parbox[t]{.15\textwidth}{%
% 		\vspace{#1\baselineskip}%
% 		#2%
% 	}%
% }

\newcommand{\movedown}[2]{%
	\vspace{#1\baselineskip}{#2}%
}

\begin{document}

\title{Dokumentace ročníkového projektu regexpové knihovny}
\author{Matěj Korvas}
\date{červenec 2010}
\maketitle

\abstract{Cílem projektu byla knihovna na efektivní vyhodnocování regulárních 
výrazů. Knihovna poskytuje zejména funkce na testování shody s~regulárním 
výrazem a na nahrazení podřetězce od\-po\-ví\-da\-jí\-cí\-ho regulárnímu výrazu.  
Kde je to teoreticky možné, používá algoritmy s~polynomiální složitostí vůči 
délce textu a regulárního výrazu. Knihovna je psána v~jazyce C.}


\section{Uživatelská část}

\subsection{Definice regulárních výrazů}
Knihovna umí v současné podobě pracovat s regulárními výrazy typu 
\term{základní} (\term{basic}) a \term{rozšířené} (\term{extended}), jak jsou 
definovány například pro program \var{grep}.\footnote{Jejich přesný popis 
najdete na manuálových stránkách programu \var{grep}.} Od zmíněné definice se 
odchylují v opakovacích konstruktech tvaru $\{\cdot,0\}$, jež připouštějí 
a interpretují jako počet opakování shora neomezený.

\subsection{Datové typy}
Knihovna zavádí pár datových typů, které figurují i v~exportovaných funkcích.  
Mezi hlavní z~nich patří:

\begin{description}
	\item[rxAnaRess] $\ldots$ prostředky pro analýzu daným regulárním výrazem 
	(regulární výraz zkompilovaný a obvěšený kandidáty na vyhovující podřetězce)
	\item[begend] $\ldots$ dvojice začátek-konec (vyhovujícího podřetězce)
	\item[begendArr] $\ldots$ pole prvků typu \var{begend}
	\item[rxFlags]	$\ldots$ sada příznaků upravujících interpretaci regulárního 
									výrazu a chování funkce \var{substitute}.
	\item[rxCandOrdering] $\ldots$ nastavení způsobu porovnávání kandidátů na 
									vyhovující podřetězec
\end{description}

Ostatní zavedené datové typy spolu s~jejich popisem lze najít v~příslušném 
hlavičkovém souboru.

\paragraph{Poznámka.} Funkce v této knihovně pracují se znaky typu 
\texttt{wchar\_t}, nikoli \texttt{char}. Kde se v této dokumentaci mluví 
o řetězcích, jsou jimi myšleny řetězce sestavené ze znaků typu 
\texttt{wchar\_t}.



\subsection{Implementované funkce}

Knihovna implementuje zejména funkce na rozpoznávání shody s~regulárním výrazem:
\begin{itemize}
	\item \var{int matches()}
	\item \var{int matchesPrec()}
\end{itemize}
a funkce na náhradu úseku odpovídajícího regulárnímu výrazu
\begin{itemize}
	\item \var{wchar\_t *substitute()}.
\end{itemize}
Dále poskytuje funkce na přesnější určování výskytů vyhovujících 
pod\-ře\-těz\-ců, zejména tyto:
\begin{itemize}
	\item \var{begend firstMatch()}
	\item \var{begend nextMatch()}
	\item \var{begend nextDisjunctMatch()}
	\item \var{begendArr allMatches()}
	\item \var{begendArr allDisjunctMatches()},
\end{itemize}
a pomocné funkce na zacházení s~regulárním výrazem:
\begin{itemize}
	\item \var{rxAnaRess *rxCompile()}
	\item \var{cleanRress()}
	\item \var{freeRress()}.
\end{itemize}
Jejich přesná činnost je popsána níže.

\subsubsection*{\var{int matches( wchar\_t * text, wchar\_t * regex, rxFlags 
flags )}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Tato funkce rozhoduje, zda nějaký podřetězec textu vyhovuje regulárnímu 
		výrazu. Probíhá co nejrychleji, negeneruje žádné informace navíc.
	\item[Argumenty] \hfill\\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[text] $\ldots$ text, v~němž se hledá vyhovující podřetězec, ukončený 
			literálem \strterm
			\item[regex] $\ldots$ regulární výraz, se kterým se má podřetězec shodovat
			\item[flags] $\ldots$ příznaky upravující zpracování regulárního výrazu 
			(jejich popis viz níže)
		\end{description}
	\item[Návratová hodnota] \hfill \\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[1] $\ldots$ pokud text odpovídá výrazu
			\item[0] $\ldots$ pokud text výrazu neodpovídá
			\item[-1] $\ldots$ vyskytla-li se chyba
		\end{description}
\end{description}

\subsubsection*{\var{int matchesPrec( wchar\_t * text, rxAnaRess resources )}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Toto je varianta předchozí funkce, která již nezahrnuje kompilování 
		regulárního výrazu. Místo toho jej dostane v~argumentu (takový, jak jej 
		vytvořila funkce \var{rxCompile()}, viz níže).

		Návratová hodnota má stejný význam jako u~funkce \var{matches()}, argumenty 
		jsou obdobné.
\end{description}

\subsubsection*{\var{begend firstMatch( wchar\_t * text, rxAnaRess resources )}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Převede prostředky pro analýzu regulárním výrazem (argument \var{resources}) 
		do stavu bez\-pros\-třed\-ně po prvním vyhovujícím podřetězci zadaného textu 
		a vrátí souřadnice tohoto prvního vy\-ho\-vu\-jí\-cí\-ho podřetězce.  Prvním 
		se rozumí první v~zadaném uspořádání kandidátů; toto téma je popsáno v~části 
		níže.  Odkaz na text se uloží do prostředků pro analýzu.
	\item[Argumenty] \hfill\\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[text] $\ldots$ text, v~němž se hledá vyhovující podřetězec, ukončený 
			literálem \strterm
			\item[resources] $\ldots$ zkompilovaný regulární výraz, se kterým se má 
			podřetězec shodovat
		\end{description}
	\item[Návratová hodnota] \hfill \\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[\var{excBegend}] $\ldots$ pokud nastane chyba
			\item[\var{invBegend}] $\ldots$ pokud text regulárnímu výrazu nevyhovuje
			\item[\var{begend matcher}] $\ldots$ pokud nenastane některý z~předchozích 
			dvou případů, funkce vrací první vyhovující podřetězec
		\end{description}
\end{description}

\subsubsection*{\var{begend nextMatch( rxAnaRess resources )}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Převede prostředky pro analýzu regulárním výrazem (argument \var{resources}) 
		do stavu bez\-pros\-třed\-ně po následujícím vyhovujícím podřetězci zadaného 
		textu a vrátí souřadnice tohoto vy\-ho\-vu\-jí\-cí\-ho podřetězce.  
		Následujícím se rozumí následující v~zadaném uspořádání kandidátů po tom, 
		který vrátila některá z~funkcí \var{firstMatch()}, \var{nextMatch()} či 
		\var{nextDisjunctMatch()} při posledním volání, nebo první vyhovující, pokud 
		tyto funkce s~tímto argumentem nebyly volány; toto téma je popsáno v~části 
		níže.

		Argumenty a návratová hodnota jsou obdobné jako u~funkce \var{firstMatch()}.
\end{description}

\subsubsection*{\var{begend nextDisjunctMatch( rxAnaRess resources )}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Převede prostředky pro analýzu regulárním výrazem (argument \var{resources}) 
		do stavu bez\-pros\-třed\-ně po následujícím dis\-junkt\-ním vyhovujícím 
		podřetězci zadaného textu a vrátí souřadnice tohoto vyhovujícího podřetězce.  
		Který vyhovující podřetězec je následující, se vyhodnocuje totožně jako 
		u~funkce \var{nextMatch()}; tato funkce ale vrací první takový, který je 
		disjunktní s~posledním, kterého funkce \var{firstMatch()}, \var{nextMatch()} 
		či \var{nextDisjunctMatch()} nalezly. Ten\-to \uv{disjunktní} kandidát může 
		začínat už od toho předělu mezi písmeny, kde končil předchozí, pokud však 
		předchozí nebyl nulové délky. Tehdy se za disjunktní považují kandidáti 
		počínaje dalším pře\-dě\-lem mezi písmeny.

		Argumenty a návratová hodnota jsou stejné jako u~funkce \var{nextMatch()}.
\end{description}

\subsubsection*{%
\begin{tabbing}
	\var{begendArr allMatches( }\=\var{wchar\_t * text, wchar\_t * regex, rxFlags 
flags,}\\
															\>\var{rxCandOrdering ordering )}
\end{tabbing}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Vrátí pole všech podřetězců daného textu vyhovujících danému regulárnímu 
		výrazu.
	\item[Argumenty] \hfill\\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[text] $\ldots$ text, v~němž se hledá vyhovující podřetězec, ukončený 
			literálem \strterm
			\item[regex] $\ldots$ regulární výraz, se kterým se má podřetězec shodovat
			\item[flags] $\ldots$ příznaky upravující zpracování regulárního výrazu 
			(jejich popis viz níže)
			\item[ordering] $\ldots$ hodnota upravující uspořádání kandidátů na 
			vyhovující podřetězec
		\end{description}
	\item[Návratová hodnota] \hfill \\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[\var{excBegendArr}] $\ldots$ pokud nastane chyba
			\item[\var{begendArr matchers}] $\ldots$ pokud chyba nenastane; když žádný 
			podřetězec textu regulárnímu výrazu nevyhoví, vrácené pole je prázdné
		\end{description}
\end{description}

\subsubsection*{\var{begendArr allMatchesPrec( wchar\_t * text, rxAnaRess 
resources )}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Toto je varianta předchozí funkce, která již nezahrnuje kompilování 
		regulárního výrazu. Místo toho jej dostane v~argumentu (takový, jak jej 
		vytvořila funkce \var{rxCompile()}, viz níže).

		Návratová hodnota má stejný význam jako u~funkce \var{allMatches()}, 
		argumenty jsou obdobné.
\end{description}

\subsubsection*{%
\begin{tabbing}
	\var{begendArr allDisjunctMatches( }\=\var{wchar\_t * text, wchar\_t * regex, 
rxFlags flags,}\\
																			\>\var{rxCandOrdering ordering )}
\end{tabbing}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Podobně jako funkce \var{allMatches()}, tato funkce vrátí pole obsahující 
		vyhovující podřetězce v~textu tak, jak by je při postupných voláních vracela 
		funkce \var{nextDisjunctMatch()}.
	\item[Návratová hodnota] \hfill \\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[\var{excBegendArr}] $\ldots$ pokud nastane chyba
			\item[\var{begendArr matchers}] $\ldots$ pokud chyba nenastane; když žádný 
			podřetězec textu regulárnímu výrazu nevyhoví, vrácené pole je prázdné
		\end{description}
\end{description}

\subsubsection*{\var{begendArr allDisjunctMatchesPrec( wchar\_t * text, 
rxAnaRess resources )}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Toto je varianta předchozí funkce, která již nezahrnuje kompilování 
		regulárního výrazu. Místo toho jej dostane v~argumentu (takový, jak jej 
		vytvořila funkce \var{rxCompile()}, viz níže).

		Návratová hodnota má stejný význam jako u~funkce \var{allDisjunctMatches()}, 
		argumenty jsou obdobné.
\end{description}

\subsubsection*{%
\begin{tabbing}
	\var{wchar\_t *substitute( }\=\var{wchar\_t * text, wchar\_t * regex, wchar\_t 
* substitute,}\\
															\>\var{rxFlags flags, rxCandOrdering ordering  )}
\end{tabbing}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Nahradí v~textu podřetězec či podřetězce vyhovující regulárnímu výrazu 
		řetězcem \var{substitute} a vrátí výsledný řetězec. (Původní zůstane 
		nezměněn.)
	\item[Argumenty] \hfill\\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[text] $\ldots$ text, ve kterém se hledá a nahrazuje vyhovující 
			podřetězec, ukončený literálem \strterm
			\item[regex] $\ldots$ regulární výraz, jemuž odpovídající podřetězce se 
			nahrazují
			\item[substitute] $\ldots$ řetězec, kterým se nahradí vyhovující podřetězec 
			či podřetězce
			\item[flags] $\ldots$ příznaky upravující zpracování regulárního výrazu 
			a udávající, zda se nahradí pouze první, nebo všechny disjunktní 
			vyhovující podřetězce (popis příznaků viz níže)
			\item[ordering] $\ldots$ hodnota upravující uspořádání kandidátů na 
			vyhovující podřetězec
		\end{description}
	\item[Návratová hodnota] \hfill \\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[\var{\NULL}] $\ldots$ pokud nastane chyba
			\item[\var{wchar\_t *afterSubst}] $\ldots$ pokud chyba nenastane, funkce 
		vrací řetězec po nahrazení
		\end{description}
\end{description}

\subsubsection*{%
\begin{tabbing}
	\var{rxAnaRess *rxCompile( }\=\var{wchar\_t * text, wchar\_t * regex, rxFlags 
flags,}\\
															\>\var{rxCandOrdering ordering )}
\end{tabbing}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Převede regulární výraz za pomoci upřesnujících příznaků do tvaru, ve kterém 
		jej používají knihovní funkce vnitřně, a přiřadí k~němu daný text 
		a uspořádání kandidátů na vyhovující podřetězce.
	\item[Argumenty] \hfill\\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[text] $\ldots$ text, který se přidruží k~regulárnímu výrazu pro 
			budoucí analýzu, ukončený literálem \strterm
			\item[regex] $\ldots$ regulární výraz, který se má zkompilovat
			\item[flags] $\ldots$ příznaky upravující zpracování regulárního výrazu 
			(jejich popis viz níže)
			\item[ordering] $\ldots$ hodnota upravující uspořádání kandidátů na 
			vyhovující podřetězec
		\end{description}
	\item[Návratová hodnota] \hfill \\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[\var{\NULL}] $\ldots$ pokud nastane chyba
			\item[\var{\var{rxAnaRess *rress}}] $\ldots$ pokud chyba nenastane, funkce 
			vrací zkompilované prostředky pro a\-na\-lý\-zu regulárním výrazem
		\end{description}
\end{description}

\subsubsection*{\var{void cleanRress( rxAnaRess resources )}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Oprostí prostředky pro analýzu regulárním výrazem od všeho, čím byly svázány 
		k~analýze konkrétního textu, a uvolní tuto pamět.
	\item[Argumenty] \hfill\\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[resources] $\ldots$ prostředky pro analýzu, které se mají oprostit 
			vazby na konkrétní text
		\end{description}
\end{description}

\subsubsection*{\var{void freeRress( rxAnaRess resources )}}

\begin{description}
	\item[Popis] \hfill\\
	\nopagebreak
		Uvolní všechnu pamět alokovanou pro prostředky pro analýzu regulárním 
		výrazem.
	\item[Argumenty] \hfill\\
	\nopagebreak
		\vspace{-\abovedisplayskip}
		\begin{description}
			\item[resources] $\ldots$ prostředky pro analýzu, které se mají uvolnit
		\end{description}
\end{description}


\subsection{Správa paměti}

U~některých funkcí musí uživatel knihovny sám dbát o~to, aby uvolnil alokovanou 
pamět. Jmenovitě to jsou funkce
\begin{itemize}
	\item \var{allMatches()}
	\item \var{allMatchesPrec()}
	\item \var{allDisjunctMatches()}
	\item \var{allDisjunctMatchesPrec()}
	\item \var{substitute()}
	\item \var{rxCompile()}.
\end{itemize}
U~funkcí, které vracejí strukturu \var{begendArr}, je třeba uvolnit pamět, na 
kterou ukazuje člen \var{mbrs} (zavoláním funkce \var{free()}). U~funkce 
\var{substitute()} je potřeba zřejmá, týká se vlastního vráceného ukazatele. Po 
zavolání \var{rxCompile()} a použití prostředků pro analýzu, které vrátí, je 
třeba tyto uvolnit pomocí funkce \var{freeRress()}.


\subsection{Příznaky}

Zpracování regulárních výrazů a chování funkce \var{substitute()} upravují 
příznaky. V~současnosti mají význam pouze tyto příznaky:
\begin{description}
	\item[\var{RF\_BASIC} vs.\ \var{RF\_EXTENDED}] $\ldots$ Rozlišují, zda se 
	regulární výraz interpretuje jako základní, nebo 
	roz\-ší\-ře\-ný\footnote{Jejich definici viz v~manuálu k~programu \var{grep}.  
	Oproti definici tam použité tato knihovna neimplementuje pouze rozsah znaků 
	(\texttt{[–]}).}.  Výchozí příznak (tj.\ pokud se místo pole příznaků dosadí 
	0) je \var{RF\_BASIC}.
	\item[\var{RF\_ICASE}] $\ldots$ Určuje, zda se shoda vyhodnocuje nehledě na 
	velikost písma. Výchozí hodnota (0) znamená, že velikost písma rozhoduje.
	\item[\var{RF\_GLOBAL}] $\ldots$ U funkce \var{substitute()} určuje, zda se 
	nahradí všechny disjunktní vyhovující pod\-ře\-těz\-ce, nebo pouze první.  
	Výchozí hodnota (0) znamená, že se nahradí pouze první vyhovující 
	pod\-ře\-tě\-zec.
	\item[\var{RF\_NOSUB}] $\ldots$ Neinterpretovat v~nahrazovacím řetězci funkci 
	\var{substitute()} zpětné reference.\footnote{V příštích verzích by tento 
	příznak měl způsobit zjednodušení zkompilovaného regulárního výrazu, a tím 
	i zrychlit práci s~ním. Zatím to ale neplatí.}
\end{description}


\subsection{Uspořádání kandidátů na vyhovující podřetězec}

V~souladu s~definicí opakovacích operátorů v~regulárních výrazech (`*', `+', 
`?', `$\{\cdot,\cdot\}$') jsou někteří kandidáti na vyhovující podřetězec více 
žádoucí než jiní. Jsou jimi ti, kteří instanciují tyto opakovací operátory 
větším počtem opakování. Aby bylo těmto operátorům učiněno zadost, je třeba je 
u~každého regulárního výrazu uspořádat podle priority. Kandidát, který má více 
opakování na opakovacím operátoru vyšší priority než jiný kandidát na vyhovující 
podřetězec, je považován za vhodnější, i kdyby ostatní opakovací operátory 
instancioval méněkrát než druhý kandidát.

Operátory opakování knihovna umožnuje řadit podle tří kritérií. Jsou jimi 
vnořenost opakovacího operátoru, levopravé pořadí operátoru v~regulárním výrazu 
a tzv.\ žravost operátoru. Protože knihovna implementuje pouze základní 
a rozšířené regulární výrazy, dojdou využití pouze první dvě kritéria, nebot 
všechny opakovací operátory jsou žravé.

Přesný popis nastavení tohoto uspořádání najdete v~příslušném hlavičkovém 
souboru.


\section{Technická část}

\subsection{Způsob implementace}

Algoritmus, na kterém knihovní funkce stojí, zpracovává vstupní text podobně 
(hladově), jako by to byl konečný automat. Oproti němu je však o~něco 
složitější.

Základní struktura, kterou se zachytí každý regulární výraz, je binární strom, 
jehož uzly od\-po\-ví\-da\-jí jednotlivým prvkům regulárního výrazu. Některé 
uzly jsou vstupní a s~každým dalším zpracovávaným znakem textu dostávají odkaz 
na nového kandidáta na vyhovující podřetězec. Kandidát zastupuje potenciální 
podřetězec vyhovující regulárnímu výrazu, který začal v~určitém předělu mezi 
znaky textu, nachází se v~určitém stavu regulárního výrazu (jako automatu) 
a nese si s~sebou historii, kolikrát instacioval jednotlivé operátory opakování 
a ve kterých předělech mezi znaky textu vstupoval do jednotlivých uzávorkovaných 
podvýrazů nebo z~nich vystupoval.  Hlavní činnost algoritmu spočívá v~tom, aby 
každý druh uzlu správně přeposílal kandidáty, kteří k~němu dospějí, na sousední 
uzly či do záhrobí.

Pro ilustraci můžeme uvést příklad, jak své kandidáty přeposílá uzel, který 
představuje operátor opakování. U~kandidátů, kteří k~němu dorazí zleva, to jest 
od předcházejícího prvku regulárního výrazu, operátor opakování zkontroluje 
počet, kolikrát jednotliví kandidáti již prošli tímto otevřeným opakováním, 
a podle toho je posílá znovu na začátek opakovaného podvýrazu nebo je případně 
klonuje a posílá k~dalšímu prvku regulárního výrazu. Zároveň všem kandidátům, 
kteří z~něj odcházejí, zvýší příslušný počet opakování v~jejich historii o~1.

Ostatní uzly se chovají v~zásadě podobně jednoduše a intuitivně. Není třeba zde 
podrobně popisovat algoritmus pro každý druh uzlu, neboť ten je nejlépe popsán 
ve zdrojovém kódu.

Za pozastavení se stojí stromová struktura, do které se regulární výraz převádí.  
Regulární výraz sám je nesporně lineární; musí tedy existovat důvod, proč se 
převádí na strom. Tím důvodem nejsou operátory opakování; ty lze zachytit 
odkazem na začátek opakovaného podvýrazu i v~rámci lineární struktury. Tím 
důvodem jsou uzávorkované podvýrazy a slučování pomocí `$|$'. Jejich vinou do 
některých prvků regulárního výrazu přicházejí kandidáti z~více různých uzlů (byť 
to je jen ze dvou). A~protože je při každém zpracovávaném znaku textu prochází 
prvky regulárního výrazu postupně v~nějakém pořadí, je přirozené uspořádat je do 
struktury, kde se mohou cesty po dvojicích spojovat. Tato struktura se potom 
s~každým vstupním znakem prochází od listů, mezi nimiž jsou vstupní uzly, podle 
hloubky až do kořene.

U~některých uzlů (jako například u~uzávorkovaných podvýrazů nebo u~operátorů 
opakování) je však třeba posílat kandidáty i do hlouběji položených uzlů. Tím se 
posune hloubka, od které se strom prochází, o~několik úrovní zpět 
a s~přeposíláním kandidátů se pokračuje na této hloubce. Je přitom potřeba 
rozlišit kandidáty, kteří už uzel, který posílá do větší hloubky, už při tomto 
vstupním znaku navštívili, a patřičně s~nimi naložit. Situace je v~tomto ohledu 
spletitější zejména u~operátorů opakování tvaru `$\{0,\cdot\}$'. Její řešení se 
ale lépe zachytí zdrojovým kódem, proto zvědavého čtenáře opět odkážu do něj.

Klíčovým cílem algoritmu této knihovny je udržovat nejmenší možné počty 
kandidátů u~každého uzlu. Toho se dosahuje vyřazováním kandidátů, kteří začínají 
od stejného indexu v~textu a dostanou se do stejného uzlu stromu, pokud některý 
z~obou má lepší historii opakování. Naneštěstí se však může stát, že historie 
opakování jsou neporovnatelné, i u~kandidátů ve stejném uzlu. Tento případ 
nastává, pokud je v~dotyčném uzlu dotyčné opakování ještě otevřené, bude-li se 
ještě měnit. Pro zachování polynomiality algoritmu by ale bylo nepřípustné 
ponechávat současně všechny kandidáty, kteří jsou neporovnatelní kvůli tomu, že 
mají otevřené opakování. Zároveň však nelze vždy předem některého z~nich 
vyřadit, protože právě a pouze on může být tím správným.

Počet kandidátů ve stromě, který by jinak mohl růst kombinatoricky 
(exponenciálně) s~počtem opakování, která mohou být otevřená současně, neboli 
s~největší vnořeností opakování operátoru, se v~této knihovně snižuje snadným 
obratem: za každou vnořenou úroveň operátorů opakování se zavádějí tzv.\ značky 
opakování\footnote{v kódu datový typ \var{repMark}}. Pro každý operátor 
opakování, index do textu a začátek kandidáta může být jedna. Značka opakování 
udržuje výčet známých počtů opakování příslušných k~jejím souřadnicím (tj.\ 
operátoru, indexu do textu a začátku kandidátů). Pokud se potom vyskytnou 
vnořená opakování, jejich značkám se přidá odkaz na značku obklopujícího 
opakování odpovídající začátku instance opakování, v~rámci níž začala instance 
opakování vnořeného operátoru. Druhé a dalším instancím vnořených opakování se 
poté místo odkazu na značku obklopujícího opakování přidá značka na začátek 
předchozí instance téhož opakování, což znamená, že lze od předchozí značky 
provést právě jedno opakování dotyčného opakovacího operátoru. Značka vždy může 
odkazovat na více různých předchozích značek, čímž se spojují možnosti plynoucí 
ze všech odkazovaných značek. Skutečný kandidát, zastupující až exponenciální 
počet možných kandidátů s~různými instanciovanými počty vnořených opakovacích 
operátorů, je potom ve stromě pouze jeden a odkazuje na nejbližší značku 
otevřeného opakování. Násobení různých počtů instanciování vnořených otevřených 
operátorů opakování se tak převádí na jejich sčítání. Příslušný kandidát je sice 
po celou dobu, kdy jsou vnořená opakování otevřená, nerozřešený, co se týče 
přesného počtu instancí opakování, ale to není ničemu na překážku. Až dorazí 
k~uzlu, který ukončuje otevřené opakování, dostane přidělen nejlepší instanciaci 
toho opakování, kterou příslušná značka opakování nabízí.

Za zmínku stojí způsob nalezení prvního vyhovujícího kandidáta, jak to provádí 
například funkce \var{firstMatch()}. Kandidáti, kteří vyhověli regulárnímu 
výrazu, se totiž řadí lexikograficky podle dvojice údajů $\langle$začátek, 
konec$\rangle$. Může se přitom stát, že stromem už zcela projdou někteří 
kandidáti začínající na pozdějším indexu do textu, zatím co někteří kandidáti 
s~dřívějším začátkem ještě ve stromě jsou. Tehdy musí výpočet pokračovat, dokud 
ze stromu nevypadnou všichni kandidáti s~menším (resp.\  nevětším) začátkem než 
vyhovující kandidát s~nejmenším začátkem.


\subsection{Časová složitost}

Časovou složitost funkcí této knihovny obsahovalo již zadání, podle nějž funkce 
musí pracovat v polynomiálním čase. V této sekci složitost jednotlivých 
knihovních funkcí rozebíráme podrobněji. Odhady složitosti pro nejhorší případ 
jsou přitom často vysoké, vyšší, než by se dalo očekávat. Zpravidla se však 
jedná o případy, které v praxi nenastanou.  Dotyčné odhady vyplývají ze způsobu 
implementace knihovny, kdy se o leckterých datových strukturách či jiných 
entitách předpokládalo, že budou velmi malé, a tedy byly implementovány jen 
velice prostě.

V této sekci rozebíráme téměř všechny funkce, které knihovna obsahuje, včetně 
těch neexportovaných. Pro důkladné pochopení tohoto textu je tedy třeba zároveň 
nahlížet i do zdrojového kódu.

Odhady složitostí jsou shrnuty v tabulce \ref{tbl:complexity}.  V tabulce 
používáme symboly s tímto významem:
\begin{description}
	\item[$T$] $\ldots$ délka textu
	\item[$R$] $\ldots$ délka regulárního výrazu
	\item[$H$] $\ldots$ počet opakovacích konstruktů (`$\{\cdot,\cdot\}$') 
						v regulárním výrazu (platí $H < R$)
	\item[$S$] $\ldots$ délka nahrazujícího výrazu (pro funkci \var{substitute})
	\item[$\Delta$] $\ldots$ maximální rozpětí počtu opakování pro opakovací 
						konstrukty (hodnotu $\Delta$ lze omezit délkou textu -- $T$ --, 
						neboť každý opakovací konstrukt může nabývat nejvýše $T + 2$ hodnot, 
						jmenovitě %
						$\{0, 1, 2, \ldots, T-2, T-1, T, \infty\}$)
	\item[$C(\var{f})$] $\ldots$ horní odhad složitosti funkce \var{f}.
\end{description}
Kromě těchto symbolů v odhadech složitosti používáme výrazy sázené 
\var{tímto-způsobem}. Ty buď odkazují na funkci knihovny, anebo na některý 
z hlavních argumentů funkce na dotyčném řádku tabulky. Pro přehlednost jsme 
upřednostnili uvádět funkce bez výčtu jejich argumentů, spoléhajíce na čtenáře, 
že podle názvu argumentu pochopí, o který se jedná.

\subsubsection*{Poznámky k odvození odhadů složitosti}

Výrazy, kterými je v tabulce \ref{tbl:complexity} složitost odhadnuta, jsou 
často samy dosti složité. Nebudeme proto rozepisovat každý jednotlivý krok 
v jejich odvozování, avšak zmíníme odhady některých hodnot, které posloužily 
jako pilíře k odvození dalších odhadů.

\paragraph{Kompilování regulárního výrazu.} Zejména toho se týká výše uvedená 
poznámka o extrémně vysokém odhadu složitosti a využití jednoduché implementace 
s předpokladem, že příslušná funkce bude pracovat jen s relativně malými 
argumenty (zde regulárními výrazy). Odhad složitosti pro funkci \var{rxCompile} 
je $\bigO(R^3)$. Je odvozen od případu, kdy dojde na procházení nejvnořenějšího 
cyklu ve funkci \var{rxCompile} maximálně-krát, to je $\bigO(R)$-krát na každé 
úrovni zanoření. V tomto cyklu se upravují odkazy na operátor opakování, který 
se otevírá vstupem do daného vrcholu. Ve zdrojovém kódu na tento cyklus 
upozorňuje komentář. Funkce dosahuje své maximální asymptotické složitosti na 
vstupech tvaru %
``{\ttfamily %
(x$|$x$|$x$|\ldots$)\{$\cdot$,$\cdot$\}\{$\cdot$,$\cdot$\}\{$\cdot$,$\cdot$\}$\ldots$}''.

\paragraph{Značky opakování.} Ty jsou indexovány třemi údaji (indexem operátoru 
opakování, začátkem kandidáta na vyhovující podřetězec a indexem do textu, ke 
kterému předělu se váží), úměrnými po řadě hodnotám $H$, $T$ a $T$. Navíc 
neumíme vyloučit současnou existenci skoro žádných dvou různých značek 
opakování, tedy jejich počet odhadujeme výrazem $\bigO(HT^2)$. Každá značka může 
být vytvořena pouze při procházení jednoho ze dvou znaků textu sousedících 
s příslušným předělem. Při jednom průchodu znaku\footnote{neboli v rámci jednoho 
volání funkce \var{processChar}} lze danou značku vytvořit nejvýše jednou 
a nejvýše jednou ji smazat. Značek opakování tedy během jednoho regulárního 
výrazu a textu existuje nejvýše $\bigO(HT^2)$. Navíc platí, že funkce 
\var{addRepMark} bude mít asymptotickou složitost úměrnou $H^1$ amortizovaně za 
všechny přidávané značky se stejnými zbývajícími dvěma souřadnicemi. To ještě 
$H$-krát snižuje odhad celkové složitosti přidávání značek. Při odebírání značky 
se procházejí všechny její odkazy na předchozí značky, jichž může být až 
$\bigO(H+T)$. Protože však předpokládáme $T \gg H$, odhadujeme režii s každým 
odebíráním značky (volání funkce \var{disposeTR}) na $\bigO(T)$. Kromě 
procházení odkazů na předchozí značky se občas i některá značka opravdu 
odstraňuje. Režii se skutečným odstraňováním bylo výhodnější odhadovat zvlášť 
s pomocí invariantu, že se každá značka odebírá nejvýše 2krát, pro celý běh 
s regulárním výrazem nad textem. Oba odhady jsou v tabulce \ref{tbl:complexity} 
zřetelně odlišeny.

\paragraph{Počet průchodů vrcholem stromu na jeden znak textu.} Tento může být 
alespoň 1 za každý vrchol, ale až $\bigO(H^2)$ u vrcholů uzavřených v $\bigO(H)$ 
úrovních operátorů opakování, které jsou tvaru $\{0,\cdot\}$. Proto jej 
odhadujeme výrazem $\bigO(1 + H^2 )$.

\paragraph{Počet kandidátů ve stromě.} Kandidáti na vyhovující podřetězec jsou 
jednoznačně určeni začátkem (potenciálně) vyhovujícího podřetězce, vrcholem ve 
stromě, u kterého jsou zavěšeni, a kde jsou na něm zavěšeni, a historií 
opakování. Právě historií opakování se ale někteří kandidáti navzájem vylučují.  
Mají-li ji uzavřenou ve všech operátorech opakování, přežívá pouze jedna 
nejlepší. Jinak může koexistovat tolik kandidátů lišících se pouze historií 
opakování, kolik různých značek opakování pro jeden (vnořený) operátor 
opakování\footnote{``pro jeden operátor opakování'' proto, že v každém vrcholu 
stromu je aktuální, otevřený nejvýše jeden operátor opakování.} mohou dohromady 
používat plus kolika různými začátky mohli instanciovat vnější, nevnořený 
operátor opakování. Jmenovitě může existovat $\bigO( \Delta + T )$ kandidátů 
lišících se pouze historií opakování. V celém stromě jich tedy dohromady může 
být $\bigO( RT( \Delta + T ) )$, což lze hruběji odhadnout také jako $\bigO( 
RT^2 )$.

\paragraph{Polynomiálnost.} Na závěr zbývá vyslovit naznačený, ale nepojmenovaný 
případ, kdy se ani tento způsob implementace nevyvaruje složitosti až 
exponenciální.  Takovým příkladem jsou regulární výrazy, které obsahují 
konstrukt tvaru `$\{<$malé číslo$>$, $<$číslo velmi velké$>\}$', neboť 
logaritmicky dlouhý zápis čísla zde může způsobit lineárně velký počet kandidátů 
koexistujících ve stromě re\-gu\-lár\-ní\-ho výrazu (kvůli hodnotě $\Delta$).  
Neboli počet kandidátů, a tím i složitost, může být exponenciální k~délce zápisu 
regulárního výrazu.  Toto je však jediný případ, kdy se stává složitost až 
exponenciální.

% Zmiňovat prostorovou složitost?

\begin{table}
	\centering
	\begin{tabular}{p{.28\textwidth}p{.5\textwidth}}
		\toprule
			\thead{Funkce} &
				\thead{Horní odhad složitosti}	\\
		\midrule
			\var{addRepMark}	& $\bigO(HRT^2)$	\\
			\var{cloneCArr}
				& $\bigO( \var{arr.limit}\cdot(H+1) )$
				\\
			\var{disposeEarlyCands}
				& $\bigO( RT(\Delta + T)\cdot C(\var{disposeCand}) )$
				\\
			\var{disposeCand}
				& $\bigO( H\cdot C(\var{disposeTR}) + 1 )$
				\\
			\var{disposeTR}
				& \parbox{.5\textwidth}{%
						\vspace{-\abovedisplayskip}%
						\begin{align*}
							\bigO( \var{repMark.nofMarks} )%
								\;(\subseteq \bigO(T))%
							& \hfill & \text{pokaždé}	\\
							{}+{}						&\\
							\bigO( HRT^2 \log(HT^2) ) && \text{za celý text}
						\end{align*}%
						\vspace{-\belowdisplayskip}%
					}
				\\
			\var{getBestRepCnt}	& $\bigO(T)$	\\
			\var{mergeCands}
				& $\bigO( (\var{arr1.limit}+\var{arr2.limit}) \cdot H + 1 )$
				\\
			\var{mergeToBest}	& $\bigO( T^2 )$	\\
			\var{openParens}	& $\bigO(R)$	\\
			\var{openReps}	& $\bigO( 1 + HT\log(HT^2) )$	\\
			\var{sendUp}
				& $\bigO( (1 + H)RT(\Delta + T) )$
				\\
			\var{sendUpToNext}
				& $\bigO( (1 + H)RT(\Delta + T) )$
				\\
		\midrule
			\movedown{2}{\var{processChar}}
				& \vspace{-\floatsep}%
					\parbox{.5\textwidth}{%
						\begin{align*}
							\bigO(\;& H^4RT^3(\Delta + T) + {} \\
								{}	& (1+H^2)(R-H)\left[(1+H)RT(\Delta+T)\right]\;) \\
								= {}& \bigO(\; H^4RT^3(\Delta + T) + (1+H^3)R^2T^2 \;)	\\
								\subseteq {}	& \bigO(\; H^4RT^4 + (1+H^3)R^2T^2 \;)
						\end{align*}%
					}
				\\
		\midrule
			\var{cleanRress}
				& $\bigO( (H+1)RT(\Delta+T)\cdot C(\var{disposeTR}) )$
				\\
			\var{freeRress}
				& $\bigO( (H+1)RT(\Delta+T)\cdot C(\var{disposeTR}) )$
				\\
			\var{rxCompile}
				& $\bigO( R^3 )$
				\\
			\movedown{1}{\var{matches}}
				& \vspace{-\floatsep}%
					\parbox{.5\textwidth}{%
						\begin{align*}
							\bigO(\;& R^3 + H^4RT^4(\Delta + T) + {} \\
											& (1+H^3)R^2T^2 + (1+H)RT^2(\Delta +T)\;)
						\end{align*}%
					}
				\\
			\var{firstMatch},\newline%
			\var{nextMatch}\newline%
			\var{nextCand}
				& \movedown{.5}{$\bigO( H^4RT^4(\Delta + T) + (1+H^3)R^2T^3 )$}
				\\
			\movedown{.5}{\var{nextDisjunctMatch},\newline%
			\var{nextDisjunctCand}}
				& \vspace{-\floatsep}%
					\parbox{.5\textwidth}{%
						\begin{align*}
							\bigO(\;& RT^2(\Delta + T) + HRT^2\log(HT^2) + {}	\\
											& H^4RT^4(\Delta + T) + (1+H^3)R^2T^3\;)
						\end{align*}%
					}%
					\vspace{-\floatsep}%
				\\
			\movedown{1}{\var{allMatches}}
				& \vspace{-\floatsep}%
					\parbox{.5\textwidth}{%
						\begin{align*}
							\bigO(\;& R^3 + (1+H)RT^2(\Delta + T) + HRT^2\log(HT^2) + {}	\\
											& C(\var{allMatchesPrec})\;)
						\end{align*}%
					}
				\\
			\var{allMatchesPrec}
				& $\bigO( H^4RT^6(\Delta + T) + (1+H^3)R^2T^5 )$
				\\
			\movedown{.5}{\var{allDisjunctMatches},\newline%
			\var{allDisjunctCands}}
				& \vspace{-\floatsep}%
					\parbox{.5\textwidth}{%
						\begin{align*}
							\bigO(\;& R^3 + (1+H)RT^2(\Delta + T) + HRT^2\log(HT^2) + {}	\\
											& C(\var{allDisjunctMatchesPrec})\;)
						\end{align*}%
					}
				\\
			\var{allDisjunctMatchesPrec},\newline%
			\var{allDisjunctCandsPrec}
				& \movedown{0}{$\bigO( H^4RT^5(\Delta + T) + (1+H^3)R^2T^4 )$}
				\\
			\movedown{.5}{\var{substitute} (all)}
				& \vspace{-\floatsep}%
					\parbox{.5\textwidth}{%
						\begin{align*}
							\bigO(\;& R^3 + H^4RT^5(\Delta + T) + {} \\
											& (1+H^3)R^2T^4 + TS\;)
						\end{align*}%
					}%
					\vspace{-\floatsep}%
				\\
			\movedown{.5}{\var{substitute} (first)}
				& \vspace{-\floatsep}%
					\parbox{.5\textwidth}{%
						\begin{align*}
							\bigO(\;& R^3 + H^4RT^4(\Delta + T) + {} \\
											& (1+H^3)R^2T^3 + S\;)
						\end{align*}%
					}%
				\\
		\bottomrule
	\end{tabular}
	\caption{Odhady složitostí knihovních funkcí}
	\label{tbl:complexity}
\end{table}

\subsection{Plánované úpravy knihovny}

Knihovna \var{rxpoly} je sice dokončená a může být užitečná, po některých 
úpravách se však může stát ještě mnohem užitečnější a cennější. Mezi první, 
které by měly přijít na řadu, jistě patří tyto:

\begin{itemize}
	\item přidat alternativní algoritmy pro běžné případy (např.\ Aho-Corrasick)
	\item přidat další třídy regulárních výrazů (Perl, Vim)
	\item snížit složitost funkcí \var{cleanRress}/\var{freeRress}.
\end{itemize}

\end{document}
